import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] dataset = new int[]{10, 4, 2, 7, 5, 19, 11, 33, 28};
        sort(dataset, 0, dataset.length-1);
        System.out.println(Arrays.toString(dataset));
    }

    private static void sort(int[] dataset, int left, int right) {
        // left == right 证明就一个元素，无需排序  left > right 不需要排、
        if (left >= right){
            return;
        }
        int temp;
        int pivot = dataset[left];
        int l = left;
        int r = right;

        while(l < r){
            // 从右向左，找小于 pivot 的数 ,如果只找小于pivot 的数可能找不到
            while(dataset[r] > pivot && r > l ){
                r--;
            }
            // 从左向右 找大于 pivot 的数，可能找不到比他大的，也要限制l范围
            while (dataset[l] < pivot && l < r){
                l++;
            }
            // 找到了交换
            temp = dataset[r];
            dataset[r] = dataset[l];
            dataset[l] = temp;
            // 这里有个 数据相同陷入死循环的问题。
            /*
                举例：
                    解决死循环。
                    因为数据交换以后，他们还是从这个位置开始比较，所以，会死循环我们只需要让 l 或 r 移动一下就行了
                    他们两个只要交换，就说明一个大一个小。
             */
            if (dataset[l] == dataset[r]){
                r--;
            }
        }
        // 到这里证明 l  和 r 重合了，将 pivot 放到这个位置
        dataset[l] = pivot;
        // 下面就是回溯的问题了。
        sort(dataset,left,l-1);
        sort(dataset,l+1,right);
    }
}
